package com.le.enhance.class6;

import org.junit.Test;

import java.util.Arrays;

/**
 * 给定一个数组arr，值可正，可负，可 0；一个整数aim，求累加 和小于等于aim的，最长子数组，
 * 要求时间复杂度O(N)
 */
public class Code_05_LongestSubarrayLessSumAwesomeSolution {
    // 思路
    // 1. 先求每个位置的最小累加和,及终止下标
    // 2. 在判断累加和是否小于aim
    public static int process(int[] arr, int aim) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[] min_sum = new int[arr.length];
        int[] min_sum_index = new int[arr.length];
        min_sum[arr.length - 1] = arr[arr.length - 1];
        min_sum_index[arr.length - 1] = arr.length - 1;
        for (int i = arr.length - 2; i >= 0; i--) {
            min_sum[i] = min_sum[i + 1] < 0 ?  arr[i] + min_sum[i + 1] : arr[i];
            min_sum_index[i] = min_sum[i + 1] < 0 ? min_sum_index[i + 1] : i;
        }
        int end = 0;
        int sum = 0;
        int len = 0;
        for (int i = 0; i < arr.length; i++) {
            while (end < arr.length && sum + min_sum[end] <= aim) {
                sum += min_sum[end];
                end = min_sum_index[end] + 1;
            }
            sum -= end > i ? arr[i] : 0;
            len = Math.max(len, end - i);
            end = Math.max(end, i + 1);
        }
        return len;
    }


    public static int[] generateArray(int num) {
        int[] arr = new int[num];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 10) - 5;
        }
        return arr;
    }

    @Test
    public void test(){
        int[] arr = generateArray(6);
//        int[] arr = {2, 4, 4, -2, 1, -2};
        System.out.println(Arrays.toString(arr));
        System.out.println(process(arr,-4));
    }
}
